package chapter01;

public class ReverseKGroup {
    //递归
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode tail=head;
        for(int i=1;i<k;i++){
            tail=tail.next;
            if(tail==null){ //剩余数小于k不翻转
                return head;
            }
        }
        tail=tail.next; //指向下一段反转链表头
        ListNode pre=null,next=null,newHead=head;
        while(head!=tail){ //头插法
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        newHead.next=reverseKGroup(tail,k);
        return pre;
    }

    //迭代
    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode source=new ListNode(-1),pre,next=null;
        source.next=head;
        int i;
        pre=source;
        while (head!=null) {
            next=head;
            for (i = 1; i <= k; i++) {
                next = next.next;
                if (next == null && i < k) {
                    return source.next;
                }
            }
            pre.next = reverse(pre, next);
            head.next=next;
            pre=head;
            head = next;
        }
        return source.next;
    }

    public ListNode reverse(ListNode pre, ListNode next) {
        ListNode tail=null,p=pre.next,q;
        while(p!=next){
            q=p.next;
            p.next=tail;
            tail=p;
            p=q;
        }
        return tail;
    }

}
